package org.myy.learn.aaa.a_哈希;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

@Slf4j
public class 两数之和 {

    //核心逻辑：key是num[i], value是下标i
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i=0; i<n; i++){
            int key = target-nums[i];
            if (map.containsKey(key)){
                return new int[]{map.get(key), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    //进阶
    public static List<List<Integer>> twoSumAdvance(int[] nums, int target) {
        List<List<Integer>> solution = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i=0; i<n; i++){
            List<Integer> list = new ArrayList<>();
            int key = target-nums[i];
            if (map.containsKey(key)){
                list.add(map.get(key));
                list.add(i);
                solution.add(list);
            }
            map.put(nums[i], i);
        }
        return solution;
    }

    //进阶
    public static List<List<Integer>> twoSumAdvance2(int[] nums, int target) {
        List<List<Integer>> solution = new ArrayList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        int n = nums.length;
        for (int i=0; i<n; i++){
            List<Integer> list = new ArrayList<>();
            int key = target-nums[i];
            if (map.containsKey(key)){
                List<Integer> values = map.get(key);
                List<Integer> temp = new ArrayList<>();
                for (Integer value : values){
                    temp.add(value);
                    temp.add(i);
                }
                list.addAll(temp);
                solution.add(list);
            }
            List<Integer> vList = map.getOrDefault(nums[i], new ArrayList<>());
            vList.add(i);
            map.put(nums[i], vList);
        }
        return solution;
    }


    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,1,4};
        int target = 5;
        int[] twoSum = twoSum(nums, target);
        List<List<Integer>> twoSumAdvance = twoSumAdvance(nums,target);
        List<List<Integer>> twoSumAdvance2 = twoSumAdvance2(nums,target);
        log.info("执行结束，twoSum={}", twoSum);
        log.info("执行结束，twoSumAdvance={}", twoSumAdvance);
        log.info("执行结束，twoSumAdvance2={}", twoSumAdvance2);
    }


//    //代码不完美版
//    public static int[] twoSum(int[] nums, int target) {
//        Map<Integer, Integer> map = new HashMap<>();
//        int n = nums.length;
//        for (int i=0; i<n; i++){
//            int key = target-nums[i];
//            if (map.containsKey(key)){
//                return new int[]{map.get(key), i};
//            } else {
//                map.put(nums[i], i);
//            }
//        }
//        return new int[0];
//    }
}
